package Sort;

/**
 * @author yyq
 * @create 2021-10-15 14:27
 * 插入排序
 * 假设数据分为一个有序表和无序表
 * 无序表的数据分别往前插入
 *  进行比较 小于前面的元素进行交换
 *  -----直到结束
 */
public class InsertionSorting {
    public static void InsertSort(int[] arr){
        //有序表 arr[0] 无序表 arr[1] -arr[length-1]
        for (int i = 1; i < arr.length; i++) {
            int loc=i;
            for(int j=i-1;j>=0;j--){
                if(arr[loc]>=arr[j]) break;
                if(arr[loc]<arr[j]){
                    int temp;
                    temp=arr[loc];
                    arr[loc]=arr[j];
                    arr[j]=temp;
                    loc=j;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a={213,2,3,2,4,5,6,7,8,21};
        InsertSort(a);
        for (int i : a) {
            System.out.println(i);
        }
    }
}
